The next generation of optical disks is known as digital-versatile disk (DVD). The CD-ROM drives on laptop and desktop PCs soon will be replaced with DVD drives. DVD has a much higher storage capacity than CD-ROM, enough that an entire motion picture can fit on a single DVD disk.
The large amount of data read during playback and the low-cost reproduction methods of optical disks increase the likelihood of encountering at least some errors on playback. Error detection and correction is thus important for CD-ROM's and DVD's. Smaller amounts of data such as stored in dynamic RAM memory often use parity--a bit is added to each data word so that the expanded word always has even or odd parity. Data from CD's and DVD's are arranged into larger blocks that have error-correction information appended. Multiple error-correction bytes allow errors to not only be detected, but also located and corrected.
FIG. 1 illustrates a DVD data block with error correction for both rows and columns. Data from DVD disk 18 is read sequentially and stored in a block of data. As the data is read from DVD disk 18, it begins filling row 0 with data bytes 1, 2, 3 . . . until 182 bytes have been read. Error-correction information (ECC) for row 0 is contained in the last ten bytes of the row. Data from DVD disk 18 then begins filling the second row (row 1) with data bytes 173, 174, etc. until a second row of 172 data bytes and 10 ECC bytes has been transferred. Additional ECC bytes for the second row are contained in the last 10 bytes of row 1.
Subsequent rows of data and row-ECC information are read from DVD disk 18 and stored in a buffer memory block until all 192 rows of data have been transferred. Finally, sixteen rows of ECC bytes are read. ECC bytes in the final 16 rows are error-correction bytes for columns of data. For example, the first ECC byte in each of the last 16 rows is for column 0, which includes data byte 1 from row 0, data byte 173 from row 1, . . . , and data byte 32681 for data row 191, a total of 192 data bytes, each from a different row.
The final ten bytes of each row in the final 16 rows contains ECC information for the final 16 rows of column ECC bytes. This ensures that errors in the column ECC bytes can be detected and corrected.
Row and Column ECC
The ECC bytes at the end of a row can be used to detect, locate, and correct one or more errors within the row, but do not contain information on errors in other rows. Sometimes errors are too numerous to be detected or corrected in a row. Then the column ECC bytes can be used to find and correct the errors that are uncorrectable by the row ECC bytes. The ECC bytes at the bottom of a column are used to detect, locate, and correct one or more errors within the column, but do not contain information on errors in other columns. Column ECC provides a redundancy to error correction, allowing more difficult errors to be corrected.
Often the data and ECC bytes from the DVD disk are stored in a temporary buffer such as a static RAM buffer. Rows and columns are read to generate syndromes for each row and for each column. Syndromes are signatures or checksums formed by using a pre-defined mathematical operator on all data bytes and ECC bytes of a row or column. Polynomial operators are often used.
The syndromes are then compared to a pre-defined signature of zero to detect any errors in the row or column. The syndromes can often be used to locate and correct a detected error. Complex algorithms such those based on Reed-Solomon code are used with the ECC bytes as is well-known in the art.
Multi-Byte Fetch for Row-Syndrome Generation--FIG. 2
FIG. 2 highlights that multiple bytes can be fetched from buffer memory for row syndrome generation. A syndrome for a row is generated by "summing" all the data and ECC bytes for a row. This "summing" is not a standard addition, but rather a complex signature-generating operation of scaling and adding the 182 bytes in a row. Multiple cycles can be used, such as by adding one byte per cycle to a running scaled sum.
Syndrome generator 10 performs the signature-generating operation as the bytes from the row are input. The buffer memory containing the data block often can read out multiple bytes per cycle. Thus FIG. 2 shows four-byte reads. In a first cycle, bytes 1, 2, 3, 4 are read from the buffer memory and operated on by syndrome generator 10. In a next memory cycle, data bytes 5, 6, 7, 8 are read from memory and accumulated by syndrome generator 10, adjusting the syndrome. Each successive memory cycle can read four bytes at once when the buffer memory is a standard 32-bit memory.
Once all 172 data bytes have been read and accumulated by syndrome generator 10, then the final 10 ECC bytes are read and accumulated. The final accumulated value in syndrome generator 10 is the row syndrome for the current row. Once the row syndrome is latched, syndrome generator 10 is cleared and the process repeated for next row.
The 172 data bytes require 172/4=43 memory access cycles, while the final 10 ECC bytes requires 2.5 memory cycles. A total of 45.5 memory access cycles are required for a 4-byte data-read width. If the buffer memory were able to read 8 bytes per cycle, then the number of cycles required is reduced by half--to 22.75 cycles. Syndrome generator 10 may only accept one byte at a time, but typically its cycle time is much less than the memory access cycle time. Thus syndrome generator 10 can process all four bytes in less that one memory cycle period.
The buffer memory can be physically written in the order shown for FIG. 1, although the row length of the physical memory can differ from that of the data block. Of course, the data and ECC bytes must be written into the buffer memory in order so that the adjacent bytes are for the same row. Otherwise, the four bytes read might not be for the same row.
Single-Byte Fetch for Column Syndrome Generation--FIG. 3
While multi-byte fetches improve row-syndrome performance, column syndromes are not able to benefit from multi-byte fetching. FIG. 3 highlights that column-syndrome generation uses inefficient single-byte fetches.
For column-syndrome generation, all of the bytes in a column are fetched from the buffer memory and input to syndrome generator 10. Only one byte from each row is needed. For column 0, byte 1 of row 0 is 1 fetched and input to syndrome generator 10. Since four bytes are always read, bytes 2, 3, 4 are also read, but not needed.
In the following memory cycle, data byte 173 is read from row 1, along with bytes 174, 175, 176. Only byte 173 is input to syndrome generator 10; fetched bytes 174, 175, 176 are discarded. For each succeeding row, one byte (at column 0) is read and input to syndrome generator 10, while three bytes are fetched and discarded (for columns 1, 2, 3).
Finally the last data byte 32,675 is read from row 191. Then during the next 16 memory cycles the 16 ECC bytes for column 0 are read and input to syndrome generator 10. After the last ECC byte has been read and accumulated by syndrome generator 10, the output from syndrome generator 10 is the column syndrome for column 0. The column syndrome can be latched, syndrome generator 10 cleared, and the process repeated for the second column. Then the second byte is input to syndrome generator 10 and the first, third, and fourth bytes discarded from each 4-byte fetch.
A total of 208 memory access cycles are required to fetch one byte from each of the 208 rows for column-syndrome generation. Using moderately wider fetches does not help, since adjacent bytes in a column are 182 bytes apart in the physical memory, separated by an entire row.
Since the data and ECC bytes are loaded into the buffer memory in row order, accessing just one byte from each row cannot take advantage of multi-byte fetching of wide memories. The adjacent column bytes are not physically adjacent to each other in the buffer memory. Wide memories fetch the multiple bytes from the same row. Also, dynamic memories are often slower to access when changing the physical rows as is often necessary for fetching column data.
What is desired is a high-speed optical-disk playback system. It is desired to use multi-byte fetches of a buffer memory when generating both row and column syndromes. A more efficient column syndrome-generation system is desired. It is desired to improve performance of column syndrome generation and fetching.